package leetcode.day_2021_3_1_2022_3_7;

/**
 * 41. 缺失的第一个正数
 * https://leetcode-cn.com/problems/first-missing-positive/
 * 输入：nums = [3,4,-1,1]
 * 输出：2
 */
public class LeetCode0041 {

    public static int firstMissingPositive(int[] nums) {
        if (nums.length == 0) return 1;

        for (int i=0; i<nums.length; i++) {
            while (nums[i] != i+1 && nums[i]>0 && nums[i]<=nums.length && nums[i]!=nums[nums[i]-1]) {
                int temp = nums[i];
                nums[i] = nums[nums[i]-1];
                nums[temp-1] = temp;
            }
        }
        if (nums[0] > 1) return 1;
        for (int i=0; i<nums.length; i++) {
            if (nums[i] != i+1) return i+1;
        }
        return nums[nums.length-1]+1;
    }

    public static void main(String[] args) {
        System.out.println(firstMissingPositive(new int[]{3, 4, -1, 1}));
        System.out.println(firstMissingPositive(new int[]{1,2,0}));
        System.out.println(firstMissingPositive(new int[]{7,8,9,11,12}));
        System.out.println(firstMissingPositive(new int[]{1}));
        System.out.println(firstMissingPositive(new int[]{1, 1}));
    }
}
